﻿// 0829train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <deque>
#include <iomanip>
#include <unordered_map>

using namespace std;

/*
编号从 0-N 排列成一个环，最大的下一个 0
请输出数字之后的第一个比它大的数，如果不存在则输出-1

输入
输入一个数字字串，数字之间使用逗号分隔，例如: 1,2,3,1；1 ≤ 字串中数字个数 ≤ 10000；
-100000≤ 每个数字值 ≤100000

输出
下一个大的数列表，以逗号分隔，例如: 2,3,6,-1,6

输入
2,5,2
输出
5,-1,5

第一个 2 的下一个更大的数是 5
数字 5 找不到下一个更大的数
第二个 2 的下一个最大的数需要循环搜索，结果也是 5
 */

class Solution01
{
public:
    vector<int>result;
    Solution01(vector<int>&num_vec)
    {
        int v_size = num_vec.size();
        vector<int>ring_vec(2 * v_size);

        //排列成一个环
        for (int i=0; i<ring_vec.size(); i++)
        {
            ring_vec[i] = num_vec[i % v_size];
        }

        result.resize(ring_vec.size());

        vector<int>stack_v;
        //之后的第一个比它大,不存在则输出-1
        for (int i=ring_vec.size()-1; i>=0; i--)
        {
	        while (!stack_v.empty() && stack_v.back()<=ring_vec[i])
	        {
                stack_v.pop_back();
	        }

            if (!stack_v.empty())
            {
	            //栈顶＞curr
                result[i] = stack_v.back();
            }
            else
            {
                result[i] = -1;
            }
            stack_v.push_back(ring_vec[i]);
        }

        for (int i=0; i<v_size; i++)
        {
            cout << result[i];
            if (i!=v_size-1)
            {
                cout << ',';
            }
        }

        //Solution01
    }
};

/*
 编号从 0~N 的箱子，每个箱子上面贴有一个数字，箱子中可能有一个黄金宝箱
 之前的所有箱子数字和，等于，之后的所有箱子数字和
第一个箱子左边部分的数字和定义为 0；
最后一个宝箱右边部分的数字和定义为 0
请帮阿里巴巴找到黄金宝箱，输出第一个满足条件的黄金宝箱编号，如果不存在黄金宝箱，请返回-1

输入描述
箱子上贴的数字列表，使用逗号分隔，例如 1,-1,0
宝箱的数量不小于 1 个，不超过 10000
宝箱上贴的数值范围不低于-1000，不超过 1000

输出描述
第一个黄金宝箱的编号

输入
2,5,-1,8,6
输出
3

下标 3 之前的数字和为：2 + 5 + -1 = 6
下标 3 之后的数字和为：6 = 6
 */

class Solution02
{
public:
    Solution02(vector<int>&num_vec)
    {
        int v_size = num_vec.size();
        vector<int>pre_sum(v_size+1);

        //初始化前缀和数组 pre_sum[i+1]=pre_sum[i]+num_vec[i]
        for (int i=0; i<pre_sum.size()-1; i++)
        {
            pre_sum[i + 1] = pre_sum[i] + num_vec[i];
        }

        int result = -1;
        for (int i=0; i<pre_sum.size(); i++)
        {
            int curr = pre_sum[i];
            //pre_sum[end]-pre_sum[i] 表示末尾的和
            int tail = pre_sum[pre_sum.size() - 1];
            int tail_sum = -1;
            if (i== pre_sum.size() - 1)
            {
                tail_sum = 0;
            }
            else
            {
                tail_sum = tail - pre_sum[i + 1];
            }

        	if (tail_sum == curr)
        	{
        		result = i;
        		break;
        	}
        }

        cout << result;
        //Solution02
    }
};

/*
 藏宝地有编号从0~N的箱子，每个箱子上面贴有箱子中藏有金币的数量
从金币数量中选出一个数字集合，并销毁贴有这些数字的每个箱子，
如果能销毁一半及以上的箱子，则返回这个数字集合的最小大小

输入描述
一个数字字串，数字之间使用逗号分隔，例如: 6,6,6,6,3,3,3,1,1,5
1 <= 数字个数 <=100000；
1 <= 数字 <=100000。

输出描述
这个数字集合的最小的长度，例如: 2

输入
1,1,1,1,3,3,3,6,6,8
输出
2

选择集合{1,8}，销毁后的结果数组为[3,3,3,6,6]，长度为 5，长度为原数组的一半。
大小为2的可行集合还有{1,3},{1,6},{3,6}。
选择6,8 集合是不可行的，它销毁后的结果数组为[1,1,1,1,3,3,3]，新数组长度大于原数组的二分之一
 */

class Solution03
{
public:
    unordered_map<int, int>statistic;
    Solution03(vector<int>&num_vec)
    {
        for (auto&num:num_vec)
        {
            statistic[num] += 1;
        }

        vector<pair<int, int>>sort_vec;

        for (auto&map_item:statistic)
        {
            sort_vec.push_back(make_pair(map_item.first, map_item.second));
        }

        sort(sort_vec.begin(), sort_vec.end(), [](pair<int,int>&a, pair<int,int>&b)
        {
                return a.second > b.second;
        });

        //销毁一半及以上
        int target_count = ceil(double(num_vec.size()) / 2);
        int result = -1;
        vector<int>tmp_vec = num_vec;
        for (int i=0; i<sort_vec.size(); i++)
        {
            int erase_num = sort_vec[i].first;
            vector<int>new_vec;
            for (auto&num:tmp_vec)
            {
                if (num == erase_num) continue;
                new_vec.push_back(num);
            }

            if (new_vec.size() <= (num_vec.size() - target_count))
            {
                result = i;
                break;
            }
            tmp_vec = new_vec;
        }
        cout << result + 1;
        //Solution03
    }
};

/*
 藏宝地有编号从0~N的箱子，每个箱子上面贴有一个数字
 查看宝箱是否存在，两个箱子上贴的数字相同，
 同时这两个箱子的编号之差的绝对值小于等于咒语数字
 如果存在这样的一对宝箱，请返回最先找到的那对宝箱左边箱子的编号，如果不存在则返回-1

输入描述
第一行输入一个数字字串，数字之间使用逗号分隔，例如: 1,2,3,1
字串中数字个数>=1，<=100000; 每个数字值>=-100000，<=100000
第二行输入咒语数字，例如: 3，咒语数字>=1，<=100000

输出描述
存在这样的一对宝箱，请返回最先找到的那对宝箱左边箱子的编号，如果不存在则返回-1

输入
6,3,1,6
3
输出
0

输入
6,3,1,6（编号之差的绝对值）
3（小于等于咒语数字）
输出
0（返回最先找到的那对宝箱左边箱子的编号，如果不存在则返回-1）

下标为0和3的两个元素6满足条件，输出较小的下标0
 */

//class Solution04
//{
//public:
//    Solution04(vector<int>&num_vec, int pos_diff)
//    {
//        //双重遍历
//        int result = -1;
//        bool is_find = false;
//        for (int i=0; i<num_vec.size(); i++)
//        {
//            //两个箱子上贴的数字相同
//            //编号之差的绝对值小于等于咒语数字
//            int curr_num = num_vec[i];
//            for (int start=i+1; start<num_vec.size();start++)
//            {
//                int back_num = num_vec[start];
//
//                if (curr_num==back_num && (start-i)<= pos_diff)
//                {
//                    result = i;
//                    is_find = true;
//                    break;
//                }
//            }
//            if (is_find) break;
//        }
//        cout << result;
//	    //Solution04
//    }
//};

class Solution14
{
public:
    unordered_map<int, int>pos_map; //val index
    Solution14(vector<int>& num_vec, int pos_diff)
    {
        int min_sum = INT_MAX;
        int result = -1;
        for (int i=0; i<num_vec.size(); i++)
        {
            int curr_num = num_vec[i];
            if (pos_map.count(curr_num)>0)
            {
                //计算pos_diff
                int curr_diff = i - pos_map[curr_num];
                int pos_sum = i + pos_map[curr_num];
                if (curr_diff <=pos_diff)
                {
                    if (pos_sum < min_sum)
                    {
                        result = pos_map[curr_num];
                        min_sum = pos_sum;
                    }
                }
                else
                {
                    pos_map[curr_num] = i;
                }
            }
            else
            {
                pos_map[curr_num] = i;
            }
        }
        cout << result;
        //Solution04
    }
};

/*
 编号从 0-N 的箱子，每个箱子上面贴有一个数字
 找出连续 k 个宝箱数字和的最大值，并输出该最大值

输入
第一行输入一个数字字串，数字之间使用逗号分隔，例如: 2,10,-3,-8,40,5
1 ≤ 字串中数字的个数 ≤ 100000
-10000 ≤ 每个数字 ≤ 10000
第二行输入咒语数字k，例如: 4，咒语数字大小小于宝箱的个数

输出
连续 k 个宝箱数字和的最大值，例如: 39

示例1
2,10,-3,-8,40,5
4
输出
39
 */
class Solution05
{
public:
    int result = 0;
    Solution05(vector<int>&num_vec, int win_length)
    {
        int first_left = 0, first_right = win_length - 1;
        int max_sum = 0;

        for (int i= first_left; i<=first_right; i++)
        {
            max_sum += num_vec[i];
        }
        result = max_sum;

        int old_left = first_left; //丢弃old_left，新增right
        for (int left=1, right=win_length; right<num_vec.size(); left++,right++)
        {
            max_sum -= num_vec[old_left];
            max_sum += num_vec[right];

            result = max(max_sum, result);
            old_left = left;
        }

        cout << result;
        //Solution05
    }
};


int main()
{
	{
        //2,10,-3,-8,40,5
        //4
        //39
        vector<int>num_vec;
        //string input = "2,10,-3,-8,40,5";
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        while (getline(oh_sstream, token, ','))
        {
            num_vec.push_back(stoi(token));
        }

        //int win_length = 4;
        int win_length;
        cin >> win_length;
        Solution05 solu(num_vec, win_length);


        return 0;
	}
	{
        vector<int>num_vec;
        //string input = "6,3,1,6";
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        while (getline(oh_sstream, token, ','))
        {
            num_vec.push_back(stoi(token));
        }

        //int target_limit = 3;
        int target_limit;
        cin >> target_limit;
        Solution14 solu(num_vec, target_limit);
        return 0;
	}
	{
        vector<int>num_vec;
        //string input = "2,2,2,2";
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        while (getline(oh_sstream,token, ','))
        {
            num_vec.push_back(stoi(token));
        }

        Solution03 solu(num_vec);

        return 0;
	}
	{
        vector<int>num_vec;
        string input = "2,5,-1,8,6";
        //string input;
        //getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        while (getline(oh_sstream, token, ','))
        {
            num_vec.push_back(stoi(token));
        }
        //cout << ceil(double(num_vec.size()) / 2);
        //Solution02 solu(num_vec);

        return 0;
	}
    vector<int>num_vec;
    //string input = "2,5,2";
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    while (getline(oh_sstream, token, ','))
    {
        num_vec.push_back(stoi(token));
    }

    Solution01 solu(num_vec);


}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
